.. SPDX-License-Identifier: GPL-2.0 or GPL-3.0
.. Copyright © 2019 Ariadne Devos

.. _speculation:

Controlling speculation
=======================

Many branches are very predictable, e.g. in a
`for(int i = 0; i < n; i++) S;` loop, so [#perf]_ some
processors, when encountering a branch, make a
guess at its direction for performance, and
rewind *most* effects when proven incorrect.

Unfortunately [#mitig]_, this opens up side-channels,
as electomagnetic radiation, power usage, acoustics,
cache effects are not reverted.

Even worse, compilers optimise as-if side-channels
did not exist.

Terminology
-----------

speculation, speculative execution:
  executing instructions while guessing branch outcomes
  incorrectly

side channel:
  a class of information leaks

  Being a leak, information does not come out of the faucet,
  filling a glass of water for drinking (desired communication),
  but rather spills on the floor, damaging the floor and futhering
  water scarcity (undesired communication).

Mitigations
-----------

`sHT_index_nospec(i, n)`:
  return the index `i`, corrected to be within bounds of an
  array of length `n`
  (<sHT/nospec.h>)

`sHT_despeculate()`:
  arrest all speculation in the current thread
  (<sHT/nospec.h>)

`sHT_index_iterate(i, n)`:
  a convenient replacement for `for(i = 0; i < n; i++)`
  (<sHT/index.h>)

`sHT_min_size(x, y)`:
  compute the minimum of `x` and `y`
  (<sHT/string.h>)

`<sHT/test.h>`:
  assembly implementations of comparison operators that the
  compiler cannot mess up

TODO: compile with -mretpoline or -findirect-thunk=???.

Verification
------------

TODO: check assembly generated by the compiler to check all
branches were wrapped correctly -- and do some mutation testing,
like SQLite does.

External resources
------------------

<https://lwn.net> has some quality journalism on the subject,
including:

*Notes from the Intelpocalypse*, by *Jake Edge*, in 2018, at
<https://lwn.net/Articles/742702/>, archived to
<ipfs://QmcLVP1y9Uc7inVSHBS3WWVWdzcG7oH8auEhTfAUh1h3ky>.

Some academic research:

*Spectre Attacks: Exploting Speculative Execution*, by many, in 2018,
<arXiv:1801.01203>, archived to
<ipfs://QmdFh3rcXgKjz7pMZpZzUU4E66FBTthSHTwofgHqwNRxKe>.

A lot more thorough analysis, specialised to Intel processors:

*Reading privileged memory with a side-channel*, by *Jahn Horn*,
*Project Zero (Google)*, in 2018, at
<https://googleprojectzero.blogspot.com/2018/01/reading-privileged-memory-with-side.html>.

If my memory serves well, someone noticed such weirdness before,
in a less formal setting, on a blog (URLs welcome!).

.. rubric:: Footnotes

.. [#perf] Apparently, this is effective. Why would these
  complexities be incurred by chip designers otherwise?
.. [#mitig] because of lessened performance incurred by mitigations,
  measured in both processor and programmer time

